package elementaryAlgorithm;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author 郭辉
 * @className TODO
 * @description 19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 *
 *
 * 提示：
 *
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 *
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 * @date 2023/4/19 15:22
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null){
            return null;
        }
        ListNode fast = head, slow = head,node = head, slowPre = null;
        for (int i = 0; fast.next != null; i++) {
            if (i >= n-1) {
                fast = fast.next;
                slowPre = slow;
                slow = slow.next;
            }else {
                fast = fast.next;
            }
        }
        if (slow == head){
            return head.next;
        }
        slowPre.next = slow.next;
        return head;
    }

    public static void main(String[] args) {
        Leet19 leet19 = new Leet19();
        //[1,2,3,4,5], n = 2
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
        ListNode node = leet19.removeNthFromEnd(node1, 2);
        System.out.println(node);
    }
}
